package lec08ds02;

public class BiLinkedList {
    static class Node {
        int data;
        Node prev;
        Node next;

        public Node(int data) {
            this(data, null, null);
        }

        public Node(int data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    Node first = new Node(0);
    Node last = new Node(0);
    int size = 0;

    BiLinkedList() {
        first.next = last;
        last.prev = first;
        size = 0;
    }

    void show() {
        Node node = first.next;
        while (node != last) {
            System.out.print(node.data + "->");
            node = node.next;
        }
        System.out.println();
    }

    void rshow() {
        Node node = last.prev;
        while (node != first) {
            System.out.print(node.data + "<-");
            node = node.prev;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BiLinkedList list = new BiLinkedList();
        for (int i = 0; i < 10; i++) {
            list.addFirst(new Node(i));
        }
        list.show();
        BiLinkedList list2 = new BiLinkedList();
        for (int i = 10; i < 20; i++) {
            list2.addLast(new Node(i));
        }
        list.show();
        list2.rshow();
        list.merge(list2);
        list.show();
        list2.show();
        ;

    }

    private void addLast(Node node) {
        insertBefore(node, last);
    }

    private void insertBefore(Node q, Node r) {
        Node p = r.prev;
        insertAfter(q, p);
    }

    //delegate
    void addFirst(Node node) {
        insertAfter(node, first);
    }

    private void insertAfter(Node q, Node p) {
        Node r = p.next;
        p.next = q;
        q.prev = p;
        q.next = r;
        r.prev = q;
        ++size;
        return;
    }

    void delete(Node q) {
        if (size == 0) return;
        Node p = q.prev;
        Node r = q.next;
        p.next = r;
        r.prev = p;
        --size;
        return;
    }

    void popFirst() {
        if (size == 0) return;
        delete(first.next);
    }

    void popLast() {
        if (size == 0) return;
        delete(last.prev);
    }

    void pushBack(Node node) {
        preInsert(node, last);
    }

    void preInsert(Node q, Node r) {
        Node p = r.prev;
        postInsert(q, p);
    }


    void postInsert(Node q, Node p) {
        Node r = p.next;
        p.next = q;
        q.prev = p;
        r.prev = q;
        q.next = r;
        ++size;
        return;
    }

    public void pushFirst(Node node) {
        postInsert(node, first);
    }

    //O(n)实现访问第k个元素
    Node get(int idx) {
        if (idx >= size) return null;
        if (idx < size >> 1) {
            Node p = first;
            while (idx-- > 0) p = p.next;
            return (p);
        } else {
            Node p = last;
            idx = size - 1 - idx;
            while (idx-- > 0) p = p.prev;
            return p;
        }

    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer("[");
        Node node = first.next;
        while (node != last) {
            buffer.append(node.data + ",");
            node = node.next;
        }
        buffer.setCharAt(buffer.length() - 1, ']');
        return buffer.toString();

    }

    void merge(BiLinkedList that) {
        last.prev.next = that.first.next;
        that.first.next.prev = last.prev.next;
        last = that.last;
        size += that.size;
    }

    void move(int distance) {

    }

}
